package com.le.high.class5;

import org.junit.Test;

/**
 * 给定一个正数数组arr，arr[i]表示第i种货币的面值，可以使用任意张。
 * 给定一个正 数aim，返回组成aim的方法数有多少种？
 */
public class Problem01_CoinsWay {

    public static int way1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return f(arr, 0, aim);
    }

    // 暴力递归
    public static int f(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        int res = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            res += f(arr, index + 1, rest - zhang * arr[index]);
        }
        return res;
    }

    public static int way2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // dp[i][j]: 使用i位置元素拼出J的方法数
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = j % arr[0] == 0 ? 1 : 0;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = j - arr[i] >= 0 ? dp[i - 1][j] + dp[i][j - arr[i]] : dp[i - 1][j];
            }
        }
        return dp[arr.length - 1][aim];
    }

    @Test
    public void test() {
        int[] coins = {10, 5, 1, 25};
        int aim = 10;
        System.out.println(way1(coins, aim));
        System.out.println(way2(coins, aim));


    }
}
